package com.myc.subjects.binarysearch;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * LeetCode题号：287
 *
 * 寻找重复数
 *
 * 给定一个包含 n + 1 个整数的数组nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。
 * 假设 nums 只有一个重复的整数，找出这个重复的数 。
 * 你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。
 *
 * 示例 1：
 * 输入：nums = [1,3,4,2,2]
 * 输出：2
 *
 * 示例 2：
 * 输入：nums = [3,1,3,4,2]
 * 输出：3
 *
 * 示例 3：
 * 输入：nums = [1,1]
 * 输出：1
 *
 * 示例 4：
 * 输入：nums = [1,1,2]
 * 输出：1
 *
 * 提示：
 * 1 <= n <= 105
 * nums.length == n + 1
 * 1 <= nums[i] <= n
 * nums 中只有一个整数出现两次或多次，其余整数均只出现一次
 *
 * 进阶：
 * 如何证明 nums 中至少存在一个重复的数字?
 * 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-the-duplicate-number
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Xunzhaochongfushu {

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3,4,2};
        Xunzhaochongfushu x = new Xunzhaochongfushu();
        System.out.println(x.findDuplicate2(nums));
    }

    /**
     * 方法一：二分查找
     * 时间复杂度：O(n*log^n)
     * 使用假想的排好序的数组进行二分查找。
     * 比较的条件是数组中小于等于i的数的个数 count，count <= i，则target在右边，count > i，则count(i)在左边，这里包括i
     */
    public int findDuplicate1(int[] nums) {
        //定义首尾指针
        int from = 1;
        int to = nums.length - 1;
        //不存在边界条件，因为这个数一定存在，所以直接开始遍历
        //遍历虚拟排好序的数组
        while(from < to){//这里相等即退出
            int mid = (from + to) / 2;

            //注意这里的判断条件在方法注释中已经注明，所以需要先获取count的值，我们只能遍历原数组获取
            int count = 0;
            for(int num : nums){
                if(num <= mid) count++;
            }

            //判断
            if(count <= mid) from = mid + 1;
            else to = mid;//这里不能-1因为可能要找的数就是mid

        }

        return to;//返回from或者to
    }

    /**
     * 方法二：快慢指针（进阶）
     * 时间复杂度：O(n)
     * 将数组每个值作为链表下个值的地址，再将从0开始的，每次增加1的数值作为链表的值，将原数组组成一个链表。
     * 如果有重复的数据，那必将导致多个地址指向了同一个值，那么就一定会形成一个环状链表结构，我们使用快慢指针来遍历这个环状结构
     */
    public int findDuplicate2(int[] nums) {
        //先使用快慢指针，并使之相遇
        int fast = 0;//快慢指针均从0开始
        int slow = 0;
        do{
            fast = nums[nums[fast]];//快指针一次走两步
            slow = nums[slow];//慢指针一次走一步
        }while(fast != slow);//使用do...while循环因为一开始fast就等于slow，先让他们走一次，再到相等时结束

        /**
         * 如何计算环的入口的位置呢(即重复数)?
         * 快指针走过的距离：起始点到环入口的距离（记为a）+ 快指针环内走过的整圈数（记为m） * 环的长度（记为c） + 环入口走到相遇点的距离（记为b）
         * 慢指针走过的距离：起始点到环入口的距离（记为a）+ 慢指针环内走过的整圈数（记为n，这里每次走一步的话应该是0） * 环的长度（记为c） + 环入口走到相遇点的距离（记为b）
         * 因为快慢指针是同时起步，同时结束，所以快指针走过的距离是慢指针的2倍，所以我们得出：
         *      a + m*c + b = 2(a + n*c + b)
         * 即       a + b = (m - 2n) * c
         * 我们把环内相遇点走到环入口的距离记为d
         * 那么则有 b + d = c 即 b = c - d
         * 于是上面的公式又可以转换为：
         *      a + c - d = (m - 2n) * c
         * 所以
         *      a = (m - 2n - 1) * c + d
         */


        //再使用两个每次都走一步的指针，再使之相遇
        int pointer1 = 0;//第一个从0开始
        int pointer2 = fast;//第二个从快慢指针的相遇点开始
        while(pointer1 != pointer2){//根据上面的数学推算这两个指针的相遇点就是环的入口点（也就是重复数）
            pointer1 = nums[pointer1];
            pointer2 = nums[pointer2];
        }

        return pointer1;
    }


    //官方题解
    //二分查找
    public int findDuplicateOfficial1(int[] nums) {
        int n = nums.length;
        int l = 1, r = n - 1, ans = -1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            int cnt = 0;
            for (int i = 0; i < n; ++i) {
                if (nums[i] <= mid) {
                    cnt++;
                }
            }
            if (cnt <= mid) {
                l = mid + 1;
            } else {
                r = mid - 1;
                ans = mid;
            }
        }
        return ans;
    }

    //二进制
    public int findDuplicateOfficial2(int[] nums) {
        int n = nums.length, ans = 0;
        int bit_max = 31;
        while (((n - 1) >> bit_max) == 0) {
            bit_max -= 1;
        }
        for (int bit = 0; bit <= bit_max; ++bit) {
            int x = 0, y = 0;
            for (int i = 0; i < n; ++i) {
                if ((nums[i] & (1 << bit)) != 0) {
                    x += 1;
                }
                if (i >= 1 && ((i & (1 << bit)) != 0)) {
                    y += 1;
                }
            }
            if (x > y) {
                ans |= 1 << bit;
            }
        }
        return ans;
    }


    //快慢指针
    public int findDuplicateOfficial3(int[] nums) {
        int slow = 0, fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }


}

/**
 * 总结：
 * 技巧：
 * 1.这题与之前的搜索二维矩阵都给二分查找提供了一个很好的思路，即在一个集合中查找某个元素时，可以将集合中的元素放在一个假想的排好序的数组中。
 * 再通过寻找自定义判断左右指针移动的条件，即target在mid的左右的条件（这道题是比较这个值与小于等于这个值的数的个数）
 *
 * 2.关于快慢指针的问题，我感觉我三言两语也说不清楚，幸好我看到有知乎大神有个不错的总结：
 *   https://zhuanlan.zhihu.com/p/151031268
 */
